/*
5.25
time:20201119 20:38 PM
key:1.取出栈顶马上弹出
user：ldc
*/

#include <iostream>
using namespace std;
#include<stack>
class Tree
{
public:
	int data;
	Tree* lchild;
	Tree* rchild;
	Tree()
	{
		data = -1;
		lchild = NULL;
		rchild = NULL;
	}
};
void write(Tree* node)
{
	if (node != NULL) 
	{
		int a;
		cin >> a;
		if (a != 0)
		{
			node->data = a;
			node->lchild = new Tree;
			node->rchild = new Tree;
		}
		write(node->lchild);
		write(node->rchild);
	}
}
void PerOrder(Tree* node)
{
	if (node != NULL)
	{
	cout << node->data << " ";
	PerOrder(node->lchild);
	PerOrder(node->rchild);
	}
}
//注意这里栈一定要是引用，否则大麻烦
void PerOrder2(Tree* node, stack<Tree*>&rchild_stack)
{
	if (node->data != -1)//当前指针不为空才继续
	{
		cout << node->data << " ";//输出数据
		if (node->rchild->data != -1)//右孩子不为空则入栈
		{
			rchild_stack.push(node->rchild);
		}
		PerOrder2(node->lchild, rchild_stack);//右孩子入栈后继续左递归
		if (!rchild_stack.empty())//左递归至尽头时开始观察栈顶元素
		{
			
			Tree*b = rchild_stack.top();//抽出栈顶元素
			rchild_stack.pop();//抽完必须马上踢出栈顶(第一次做就是左递归再踢出，就不能保证每个元素只进或出栈一次。
			PerOrder2(b, rchild_stack);//对这个抽出来的元素进行左递归
		}
	}
}
//完全由栈实现的先序遍历
void PerOrder3(Tree* node, stack<Tree*>& child_stack)
{
	child_stack.push(node);
	while (!child_stack.empty())
	{
		Tree* b = child_stack.top();
		child_stack.pop();
		if (b->data != -1) 
		{
			cout << b->data << " ";
			child_stack.push(b->rchild);
			child_stack.push(b->lchild);
		}
	}
}
int main()
{
	Tree* head = new Tree;
	stack<Tree*>rchild_stack;
	stack<Tree*>child_stack;

	//使用一下输入
	//1 2 3 0 0 4 0 5 0 0 6 0 7 0 8 0 0
	write(head);
	cout << "先序遍历输出树(-1是空节点)" << endl;
	PerOrder(head);
	cout << "\n改写PO算法1	一个栈一个递归" << endl;
	PerOrder2(head, rchild_stack);
	cout << "\n改写PO算法2	完全由栈实现的先序遍历：" << endl;
	PerOrder3(head, child_stack);

}




